package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/count-complete-tree-nodes/">完全二叉树的节点个数(Count Complete Tree Nodes)</a>
 * <p>给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。</p>
 * <p><a href="https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin">完全二叉树</a>的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4,5,6]
 *      输出：6
 *
 * 示例 2：
 *      输入：root = []
 *      输出：0
 *
 * 示例 3：
 *      输入：root = [1]
 *      输出：1
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目范围是[0, 5 * 10^4]</li>
 *     <li>0 <= Node.val <= 5 * 10^4</li>
 *     <li>题目数据保证输入的树是 完全二叉树</li>
 * </ul>
 * </p>
 * <b>进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？</b>
 *
 * @author c2b
 * @since 2023/10/18 13:59
 */
public class LC0222CountCompleteTreeNodes_M {

    static class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            // leftHeight == rightHeight：说明左子树一定是满的，因为节点已经填充到右子树
            // 左子树的节点总数可直接得到：`2^leftHeight -1`，再加上根节点的1，正好是`2^leftHeight`。再对右子树进行递归统计
            if (leftHeight == rightHeight) {
                return countNodes(root.right) + (1 << leftHeight);
            }
            // leftHeight != rightHeight：说明最后一层不满，但倒数第二层一定是满的，
            // 右子树的节点个数可直接得到：`2^rightHeight -1`，再加上根节点的1，正好是`2^rightHeight`。再对左子树进行递归查找。
            else {
                // 说明左子树比右子树多一层，上一层的右子树一定是满的。
                return countNodes(root.left) + (1 << rightHeight);
            }
        }

        //private int getHeight(TreeNode node) {
        //    if (node == null) {
        //        return 0;
        //    }
        //    return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        //}

        private int getHeight(TreeNode node) {
            int level = 0;
            while (node != null) {
                ++level;
                node = node.left;
            }
            return level;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        //root.left.right = new TreeNode(5);
        //root.right.left = new TreeNode(6);
        System.out.println(solution.countNodes(root));
    }
}